package org.parngon.maze;

public class FlashSort
{
  public static void flashsort(FlashSortable arr[])
  {
    //Number of groups into which the elements are classified
    //Neubert suggests 0.2 to 0.5 times the number of elements in the array.
    int num_groups = (int) (0.4 * arr.length);
   
    //Count the number of elements in each group
    int groups[] = new int[num_groups];
    
    flashsort(arr, num_groups, groups);
  }
   
  public static void flashsort(FlashSortable arr[], int num_groups, int groups[])
  {
    //First get the minimum and maximum values
    int min = arr[0].sortOrder();
    int max_idx = 0;
    int i;
    for ( i = arr.length - 1; i > 0; i-- ) {
      if ( arr[i] == null ) {
        System.out.println("arr[" + i + "] is null!!!");
        System.exit(1);
      }
      if ( arr[i].sortOrder() < min ) min = arr[i].sortOrder();
      if ( arr[i].sortOrder() > arr[max_idx].sortOrder() ) max_idx = i;
    }

    //If they are the same, all elements are identical
    //so the array is already sorted.
    if ( min == arr[max_idx].sortOrder() ) return;
  
    //Count the number of elements in each group.
    //Take care to handle possible integer overflow by
    //casting to larger datatypes where this might occur.
    double scaling_constant = (num_groups - 1) / (((double)arr[max_idx].sortOrder()) - min);
    int group;
    for ( i = arr.length - 1; i >= 0; i-- ) {
      group = (int)(scaling_constant * (((long)arr[i].sortOrder()) - min));
      groups[group]++;
    }
  
    //Set the groups to point to the indexes in the array
    //that are the last index for each group.
    groups[0]--;
    for ( i = 1; i < groups.length; i++) {
      groups[i] += groups[i - 1];
    }
  
    //Put the biggest element at index 0 so that the swapping
    //algorithm below starts on the largest element & max group.
    FlashSortable old_value = arr[max_idx];
    arr[max_idx] = arr[0];
    arr[0] = old_value;
  
    //start with element at index 0
    int idx = 0;
    //and the maximum group
    group = num_groups - 1;
   
    //Start moving elements into their groups.
    //We need to make 'arr.length' moves at most,
    //but if we have one move left in the outer loop
    //then the remaining element is already in the right place,
    //so we need test for only 'arr.length-1' moves.
    int number_of_moves_left = arr.length - 1;
  
    FlashSortable new_value;
    while ( number_of_moves_left > 0 ) {
      //When the first group fills up, we start scanning
      //for elements left in the wrong groups, and move them.

      //Note that we scan through the whole object array only once.
      while ( idx > groups[group] ) {
        idx++;
        group = (int)(scaling_constant * (((long)arr[idx].sortOrder()) - min));
      }

      new_value = arr[idx];
      //We run this loop until the first group fills up.
      //Then we run the previous scan loop to get back into this loop.
      while ( idx != groups[group] + 1 ) {
        group = (int)(scaling_constant * (((long)new_value.sortOrder()) - min));
        old_value = arr[groups[group]];
        arr[groups[group]] = new_value;
        new_value = old_value;
        groups[group]--; //decrement the pointer to the next index
        number_of_moves_left--;
      }
    }

    //Now we have our partially ordered array,
    //we do an insertion sort to order the remainder.
    for ( i = arr.length - 3; i >= 0; i-- ) {
      if ( arr[i + 1].sortOrder() < arr[i].sortOrder() ) {
        old_value = arr[i];
        idx = i;
        while ( arr[idx + 1].sortOrder() < old_value.sortOrder() ) {
          arr[idx] = arr[idx + 1];
          idx++;
        }
        arr[idx] = old_value;
      }
    }
  }

  public static void main(String argv[])
  {
    FlashSortable a[] = new FlashSortable[50];
    for ( int i = 0; i < a.length; i++ ) {
      a[i] = new FlashSortable() {
        int so = (int)(Math.random() * 50);

        public int sortOrder()
        {
          return so;
        }

        public String toString()
        {
          return String.valueOf(so);
        }
      };
    }

    for ( FlashSortable f: a ) {
      System.out.print(f + " ");
    }
    System.out.println();

    FlashSort.flashsort(a);

    for ( FlashSortable f: a ) {
      System.out.print(f + " ");
    }
    System.out.println();
  }
}
